package dp;

import org.junit.Test;

public class FourKeysKeyboard651 {

    @Test
    public void test() {
        for (int i = 1 ; i < 40; i++) {
            OtherAnswer.maxA(i);
            maxA(i);
        }
    }

    // 这个方法有问题, 变成贪心了
    public int maxA(int N) {
        // 当前num最大的step序列, 下标从1开始
        StepResult[] dp1 = new StepResult[N+1];

        // 当前num+buf最大的step序列, 下标从1开始
        StepResult[] dp2 = new StepResult[N+1];

        dp1[0] = new StepResult(0, 0);
        dp2[0] = dp1[0];

        // 循环内临时变量
        StepResult t1 = new StepResult(0, 0);
        StepResult t2 = new StepResult(0, 0);
        StepResult t3 = new StepResult(0, 0);

        // 模拟每次操作
        for (int i = 1; i <= N; i++) {
            // 直接按A
            t1.num = dp1[i-1].num + 1;
            t1.buf = dp1[i-1].buf;

            // 按CTRL-V
            t2.num = dp2[i-1].num + dp2[i-1].buf;
            t2.buf = dp2[i-1].buf;

            if (i >= 3) {
                // 连续按 CTRL-A, CTRL-C, CTRL-V
                t3.num = dp1[i-3].num * 2;
                t3.buf = dp1[i-3].num;
            } else {
                // 清空, 便于后续比较
                t3.num = 0;
                t3.buf = 0;
            }

            StepResult s1 = t1;
            s1 = (t2.num > s1.num) ? t2 : s1;
            s1 = (t3.num > s1.num) ? t3 : s1;

            StepResult s2 = t1;
            s2 = (t2.num + t2.buf > s2.num + s2.buf) ? t2 : s2;
            s2 = (t3.num + t3.buf > s2.num + s2.buf) ? t3 : s2;

            // 拷贝赋值
            dp1[i] = new StepResult(s1.num, s1.buf);
            dp2[i] = new StepResult(s2.num, s2.buf);
        }
        System.out.format("MyAnswer: N: %d, max: %d\n", N, dp1[N].num);
        for (int i = 1; i <= N; i++) {
            System.out.format("i: %d, dp1: %s, dp2: %s\n", i, dp1[i], dp2[i]);
        }
        System.out.println();
        return dp1[N].num;
    }

    static class StepResult {
        int num; // 当前屏幕的字符数
        int buf; // 当前缓冲区大小, 由最近一次CTRL-C产生

        public StepResult(int num, int buf) {
            this.num = num;
            this.buf = buf;
        }

        @Override
        public String toString() {
            return String.format("num: %d, buf: %d", num, buf);
        }
    }

    // copied from: https://www.cnblogs.com/xym4869/p/12591717.html
    public static class OtherAnswer {
        public static int maxA(int N) {
            if (N <= 1)
                return N;
            int[] dp = new int[N + 1];
            dp[0] = 0;
            for (int i = 1; i <= N; i++) {
                dp[i] = dp[i - 1] + 1;//按 A 键
                //全选 & 复制 dp[j-2]，连续粘贴 i - j 次
                for (int j = 2; j < i; j++) {
                    //屏幕上共 dp[j - 2] * (i - j + 1) 个 A
                    dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1));
                }
            }
            System.out.format("OtherAnswer: N: %d, max: %d\n", N, dp[N]);
            return dp[N];
        }
    }
}
